package com.demo.java.OD601_650.OD615;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【等和子数组最小和(A卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146861681
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = Integer.parseInt(in.nextLine()); // 读取数组长度
        String[] input = in.nextLine().split(" ");
        int[] nums = new int[count];
        int sum = 0;

        // 解析输入数组并求和
        for (int i = 0; i < count; i++) {
            nums[i] = Integer.parseInt(input[i]);
            sum += nums[i];
        }

        // 从最大的子集数量开始尝试
        for (int k = count; k >= 1; k--) {
            if (sum % k == 0 && canPartitionKSubsets(nums, k, sum)) {
                System.out.println(sum / k);
                break;
            }
        }
    }

    // 判断是否可以划分为k个和相等的子集
    public static boolean canPartitionKSubsets(int[] nums, int k, int totalSum) {
        int target = totalSum / k;
        int n = nums.length;
        Arrays.sort(nums); // 先排序有助于后续剪枝
        if (nums[n - 1] > target) return false; // 最大元素不能超过目标值

        boolean[] dp = new boolean[1 << n]; // 状态压缩数组，表示哪些数字被使用
        int[] curSum = new int[1 << n]; // 记录当前状态下已组成的子集和
        dp[0] = true;

        for (int state = 0; state < (1 << n); state++) {
            if (!dp[state]) continue; // 如果该状态不合法，跳过

            for (int j = 0; j < n; j++) {
                if (((state >> j) & 1) == 1) continue; // 第j个元素已用

                int next = state | (1 << j); // 将第j个元素加入新状态

                if (curSum[state] + nums[j] > target) break; // 超过目标值，剪枝

                if (!dp[next]) {
                    dp[next] = true;
                    curSum[next] = (curSum[state] + nums[j]) % target;
                }
            }
        }
        return dp[(1 << n) - 1]; // 所有元素都用完，且能成功划分
    }
}